package 回溯法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 解数独 {
    static String[][] board = { {"5","3",".",".","7",".",".",".","."},
                                {"6",".",".","1","9","5",".",".","."},
                                {".","9","8",".",".",".",".","6","."},
                                {"8",".",".",".","6",".",".",".","3"},
                                {"4",".",".","8",".","3",".",".","1"},
                                {"7",".",".",".","2",".",".",".","6"},
                                {".","6",".",".",".",".","2","8","."},
                                {".",".",".","4","1","9",".",".","5"},
                                {".",".",".",".","8",".",".","7","9"}};
    static String[] number = {"1","2","3","4","5","6","7","8","9"};
    static List<Map<String,String>> listRow = new ArrayList<>(); // 行Map
    static List<Map<String,String>> listCloum = new ArrayList<>(); // 列Map
    static List<Map<String,String>> listSquare = new ArrayList<>(); // 方格Map
    static int[][] maping = {{0,1,2},{3,4,5},{6,7,8}};
    public static void main(String[] args) {
        solveSudoku(board);
    }

    static public void solveSudoku(String[][] board) {
        int row = board.length;
        int cloum = board[0].length;
        listRow.clear();
        listCloum.clear();
        listSquare.clear();
        // 行 列
        for (int i = 0; i < row; i++) {
            Map<String,String> mapRow = new HashMap<>();
            Map<String,String> mapCloum = new HashMap<>();
            for (int j = 0; j < cloum; j++) {
                if(board[i][j] != "."){
                    mapRow.put(board[i][j],"1");
                    mapCloum.put(board[j][i],"1");
                }
            }
            listRow.add(i,mapRow);
            listCloum.add(i,mapCloum);
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                Map<String,String> mapSquare = new HashMap<>();
                for (int k = i*3; k < i*3+3; k++) {
                    for (int l = j*3; l < j*3+3; l++) {
                        if(board[k][l] != "."){
                            mapSquare.put(board[k][l],"1");
                        }
                    }
                }
                listSquare.add(maping[i][j],mapSquare);
            }
        }
        System.out.println(listRow.size());
        System.out.println(listRow);
        System.out.println(listCloum.size());
        System.out.println(listCloum);
        System.out.println(listSquare.size());
        System.out.println(listSquare);

        fun1(0);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j]+"\t");
            }
            System.out.println();
        }

    }
    public static void fun1(int n){
        if(n == 9){
            return;
        }
        for (int l = 0; l < 9; l++) { // 控制列
            for (int j = 0; j < number.length; j++) {
                if(board[n][l] == "." && check(number[j],n,l)){
                    board[n][l] = number[j];
                    listRow.get(n).put(number[j],"1" );
                    listCloum.get(l).put(number[j],"1" );
                    listSquare.get(maping[n/3][l/3]).put(number[j],"1" );
                    fun1(n+1);
                    board[n][l] = ".";
                    listRow.get(n).remove(number[j]);
                    listCloum.get(l).remove(number[j]);
                    listSquare.get(maping[n/3][l/3]).remove(number[j]);
                }
            }
        }
    }
    // public static void fun(int h,int l){
    //     if(h == 9 && l == 9){
    //         return;
    //     }
    //     if(board[h][l] == "."){
    //         for (int j = 0; j < number.length; j++) {
    //             if(check(number[j],h,l)){
    //                 board[h][l] = number[j];
    //                 listRow.get(h).put(number[j],"1" );
    //                 listCloum.get(l).put(number[j],"1" );
    //                 listSquare.get(maping[h/3][l/3]).put(number[j],"1" );
    //                 if(l == 9)
    //                     fun(h+1,0);
    //                 else
    //                     fun(h,l+1);
    //                 listRow.get(h).remove(number[j]);
    //                 listCloum.get(l).remove(number[j]);
    //                 listSquare.get(maping[h/3][l/3]).remove(number[j]);
    //             }
    //         }
    //     }
    //     else {
    //         if(l == 9)
    //             fun(h+1,0);
    //         else
    //             fun(h,l+1);
    //     }
    //
    // }

    public static boolean check(String str,int i,int j){
        boolean isOk = false;
        if(null == listRow.get(i).get(str) && null == listRow.get(j).get(str) && null == listRow.get(maping[i/3][j/3]).get(str)){
            isOk = true;
        }
        return isOk;
    }
}
